import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;
import java.util.Scanner;

/**
 * @author: gao
 * @create-date: 2025/3/18 8:43
 */

public class Solution {
    public List<List<Integer>> threeSum(int[] nums) {
        List<List<Integer>> ret = new ArrayList<>();

        //1.先排序
        Arrays.sort(nums);

        int n = nums.length;
        //2.先固定第一个数
        for (int i = 0; i < n;) {
            if(nums[i] > 0)
                break;
            int left = i+1,right = n-1,target = -nums[i];

            //3.利用两数之和
            while(left < right){
                int sum = nums[left] + nums[right];
                if(sum > target){
                    right--;
                } else if (sum < target) {
                    left++;
                }else {
                    ret.add(new ArrayList<Integer>(Arrays.asList(nums[i],nums[left],nums[right])));
                    //缩小区间
                    left++;
                    right--;

                    //去重操作
                    while(left < right && nums[left] == nums[left-1])
                        left++;
                    while(left < right && nums[right] == nums[right+1])
                        right--;
                }
            }
            i++;
            while(i < n && nums[i] == nums[i-1])
                i++;
        }
        return ret;
    }

    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        int[] nums = {-1,0,1,2,-1,-4};
        Solution solution = new Solution();
        System.out.println(solution.threeSum(nums));
    }
}